package 树;

import java.util.LinkedList;
import java.util.TreeMap;

public class _297_二叉树的序列化与反序列化 {
    public class TreeNode {
       int val;
       TreeNode left;
       TreeNode right;
       TreeNode(int x) { val = x; }
    }

    String NULL = "#";
    // 输入一个根节点，返回这个二叉树序列化的字符串
    public String serialize(TreeNode root) {
       StringBuilder sb = new StringBuilder();
       traverse(root,sb);

       return sb.toString();
    }

    void traverse(TreeNode root,StringBuilder sb){
      if(root == null){
         sb.append(NULL).append(",");
         return;
      }

       traverse(root.left,sb);
       traverse(root.right,sb);

       sb.append(root.val).append(",");
    }

    // Decodes your encoded data to tree.
    public TreeNode deserialize(String data) {
       LinkedList<String> nodes = new LinkedList<>();
       for (String s : data.split(",")) {
          nodes.add(s);
       }
       return deserialize(nodes);
    }

    TreeNode deserialize(LinkedList<String> nodes){
        if(nodes.isEmpty()) return null;

        String rootStr = nodes.removeLast(); //拿到根节点
        TreeNode root = new TreeNode(Integer.parseInt(rootStr));

        root.right = deserialize(nodes);
        root.left = deserialize(nodes);

        return root;
    }
}
